/**
 * https://leetcode-cn.com/problems/combination-sum/
 * 组合总和
 * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
 * @param candidates
 * @param target
 */
const combinationSum = (candidates: number[], target: number): number[][] => {
  const ans: number[][] = [];

  const cur: number[] = [];

  const len = candidates.length - 1;

  /**
   * 剩余选后剩余的值
   * @param left
   * @param e 边界
   */
  const dfs = (left: number, e: number) => {
    // 小于0了但是还没找到
    if (e < 0 && left !== 0) return;

    // 剩余为0, 说明可以选
    if (left === 0) {
      ans.push([...cur]);
      return;
    }

    for (let i = e; i >= 0; i--) {
      if (candidates[i] <= left) {
        cur.push(candidates[i]);

        // 选下一层
        dfs(left - candidates[i], i);

        // 删除最后一个元素
        cur.pop();
      }
    }
  };

  dfs(target, len);
  return ans;
};

combinationSum([2, 3, 6, 7], 7);
combinationSum([1], 1);
combinationSum([2, 3, 5], 8);
